package l.l.w.leetcode._047PermutationsII;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * Created by llw on 2017/11/20.
 */
public class Solution2 {
    public List<List<Integer>> permuteUnique(int[] nums) {
        if(nums == null || nums.length == 0)
            return Collections.emptyList();
        int len = nums.length;
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> list = new ArrayList<>(len);
        for (int n : nums)
            list.add(n);
        res.add(list);
        for(int i = 1; i< len; i++){
            int size = res.size();
            for(int j = 0; j < size; j++){
                list = res.get(j);
                // [1,1,2,2], when need to add the 2nd 2, it can only be added after the first 2
                for(int k = i-1; k >=0; k--){ //Important: descending order
                    if(list.get(k) == list.get(i))
                        break;
                    if(list.get(i) != list.get(k))
                        res.add(swap(list, k, i));
                }
            }
        }
        return res;
    }

    // return a new list with i, j swapped
    private List<Integer> swap(List<Integer> list, int i, int j){
        List<Integer> res = new ArrayList<>(list);
        int tmp = res.get(i);
        res.set(i, list.get(j));
        res.set(j, tmp);
        return res;
    }

    public static void main(String[] args) {
        int[] a = {-1,2,0,-1,1,0,1};
        List<List<Integer>> result = new Solution2().permuteUnique(a);
        System.out.println(result.size());
        System.out.println(result);
    }
}
